package noth.li.sort;


/**
 * 选择排序
 * <p>
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 重复第二步，直到所有元素均排序完毕。
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {7, 5, 88, 6, 99, 55, 22, 35, 57, 89, 10, 999, 29, 762, 11, 22, 3, 45, 2, 2, 2, 2, 1, 3, 21, 1};

        selectionSortAsc(arr);
        //selectionSortDesc(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 选择排序-升序
     *
     * @param arr 排序的数组
     */
    public static void selectionSortAsc(int[] arr) {

        //每次循环前面几个都不用排序了,因为肯定是最小的
        //所以用j来记录排序的次数,最多也就
        //int[] arr = {7, 5, 88, 6, 99, 55, 22, 35, 57, 89, 10, 999, 29, 762, 11, 22, 3, 45, 2, 2, 2, 2, 1, 3, 21, 1};
        for (int j = 0; j < arr.length - 1; j++) {
            int min_index = j;//记录最小值为数组首尾
            for (int i = j + 1; i < arr.length; i++) { //不用自己和自己比较
                //如果当前数比最小的数小,则最小的数修改为当前数
                if (arr[i] < arr[min_index]) {
                    min_index = i;
                }
            }
            //执行完成后,最小的数与数组首尾交换位置
            int temp = arr[j];
            arr[j] = arr[min_index];
            arr[min_index] = temp;
        }
    }

    /**
     * 选择排序-降序
     *
     * @param arr 排序的数组
     */
    public static void selectionSortDesc(int[] arr) {

        //每次循环前面几个都不用排序了,因为肯定是最小的
        //所以用j来记录排序的次数,最多也就
        for (int j = 0; j < arr.length - 1; j++) {
            int max_index = j;//记录最小值为数组首尾
            for (int i = j + 1; i < arr.length; i++) { //不用自己和自己比较
                //如果当前数比最大的数大,则最大的数修改为当前数
                if (arr[i] > arr[max_index]) {
                    max_index = i;
                }
            }
            //执行完成后,最小的数与数组首尾交换位置
            int temp = arr[j];
            arr[j] = arr[max_index];
            arr[max_index] = temp;
        }
    }
}
